package leetcode.l2;

/**
 * @author daiql
 * @description 两数相加
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * 示例：
 *
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 *
 * @date 2020/7/24 14:32
 */
public class AddTwoNumbers {

    public static void main(String[] args) {
        ListNode l1 = new ListNode();
        l1.val = 2;
        ListNode l12 = new ListNode();
        l12.val = 4;
        ListNode l13 = new ListNode();
        l13.val = 3;
        l1.next = l12;
        l12.next = l13;
        print(l1);
        ListNode l2 = new ListNode();
        l2.val = 5;
        ListNode l22 = new ListNode();
        l22.val = 6;
        ListNode l23 = new ListNode();
        l23.val = 4;
        l2.next = l22;
        l22.next = l23;
        print(l2);
//        ListNode result = solution(l1, l2);
        ListNode result = solution2(l1, l2);
        print(result);
    }

    static ListNode solution(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        int x1 = 0, x2 = 0;
        int n = 1;
        while (l1 != null && l2 != null) {
            x1 += l1.val * n;
            x2 += l2.val * n;
            n = 10 * n;
            l1 = l1.next;
            l2 = l2.next;
        }

        int sum = x1 + x2;
        String resultStr = String.valueOf(sum);
        ListNode midNode = new ListNode();
        for (int i = resultStr.length() - 1; i >= 0; i--) {
            ListNode node = new ListNode();
            node.val = Integer.parseInt(resultStr.substring(i, i+1));
            if ( i == resultStr.length() - 1) {
                result = node;
            }
            midNode.next = node;
            midNode = node;
        }

        return result;
    }

    static ListNode solution2(ListNode l1, ListNode l2) {
        ListNode midNode = new ListNode(0);
        ListNode result = midNode;
        int mid = 0;
        while (l1 != null && l2 != null) {

            int sum = l1.val + l2.val + mid;

            if (sum >= 10) {
                mid = 1;
            } else {
                mid = 0;
            }
            midNode.next = new ListNode(sum%10);
            midNode = midNode.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        return result.next;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
        ListNode() {}
    }

    static void print(ListNode result ) {

        while (result != null ) {
            System.out.print(result.val);
            if (result.next != null) {
                System.out.print(" -> ");
                result = result.next;
            } else {
                break;
            }
        }
        System.out.println("");

    }

}
